#ifndef HASHTABLE_H
#define HASHTABLE_H

#include <functional>
#include <iostream>
#include <vector>

template<class Key, class Data>
struct HashEntry
{
    HashEntry() : key(), data(), next(~0) {}
    
    Key key;
    Data data;
    int next;
};

// a useful core hash function
inline unsigned int hash(unsigned int k)
{ return k*2654435769u; }

// default hash function object
struct DefaultHashFunction
{
    template<typename Key>
    unsigned int operator() (const Key &k) const { return hash(k); }
};

struct equal
{
    template<typename T>
    bool operator() (const T &a, const T &b) const { return a==b; }
};

template<typename Key, typename Data, class HashFunction=DefaultHashFunction, class KeyEqual=equal>
struct HashTable
{
    unsigned int table_rank;
    unsigned int table_bits;
    std::vector<int> table;
    unsigned int num_entries;
    std::vector<HashEntry<Key, Data> > pool;
    int free_list;
    const HashFunction hash_function;
    const KeyEqual key_equal;
    
    explicit HashTable(unsigned int expected_size=64)
    :  table_rank(static_cast<unsigned int>(~0)), table_bits(static_cast<unsigned int>(~0)), table(0), num_entries(static_cast<unsigned int>(~0)), pool(), free_list(static_cast<unsigned int>(~0)),
    hash_function(HashFunction()), key_equal(KeyEqual())
    { init(expected_size); }
    
    explicit HashTable(const HashFunction &hf, unsigned int expected_size=64)
    : hash_function(hf), key_equal(KeyEqual())
    { init(expected_size); }
    
    void init(unsigned int expected_size)
    {
        unsigned int i;
        num_entries=0;
        table_rank=4;
        while(1u<<table_rank < expected_size)
            ++table_rank;
        ++table_rank; // give us some extra room
        table_bits=(1u<<table_rank)-1;
        table.resize(1u<<table_rank);
        for(i=0; i<table.size(); ++i)
            table[i]=-1; // empty list
        pool.resize(1u<<table_rank);
        free_list=0;
        for(unsigned int j=0; j<pool.size()-1; ++j)
            pool[j].next=j+1;
        pool[pool.size()-1].next=-1; // end of free list
    }
    
    void add(const Key &k, const Data &d)
    {
        if(free_list==-1)
            reserve(1u<<(table_rank+1));
        int i=free_list; // where we're going to put the new entry
        free_list=pool[i].next;
        unsigned int t=hash_function(k)&table_bits; // index into table
        pool[i].key=k;
        pool[i].data=d;
        pool[i].next=table[t]; // put the new entry at the start of table[t]'s list
        table[t]=i;
        ++num_entries;
    }
    
    void delete_entry(const Key &k, const Data &d) // delete first entry that matches both key and data
    {
        unsigned int t=hash_function(k)&table_bits;
        int i=table[t], *p_i=&table[t];
        while(i!=-1){
            if(key_equal(k, pool[i].key) && d==pool[i].data){
                *p_i=pool[i].next; // make list skip over this entry
                pool[i].next=free_list; // and put it on the front of the free list
                free_list=i;
                return; // and we're done
            }
            p_i=&pool[i].next;
            i=*p_i;
        }
    }
    
    unsigned int size() const
    { return num_entries; }
    
    void clear()
    {
        unsigned int i=0;
        num_entries=0;
        for(i=0; i<table.size(); ++i)
            table[i]=-1; // empty list
        free_list=0;
        for(i=0; i<pool.size()-1; ++i)
            pool[i].next=i+1;
        pool[pool.size()-1].next=-1;
    }
    
    void reserve(unsigned int expected_size)
    {
        if(expected_size<=pool.size())
            return;
        while(1u<<table_rank < expected_size)
            ++table_rank;
        table_bits=(1u<<table_rank)-1;
        // increase room for new entries
        unsigned int old_size=(unsigned int)pool.size(), i;
        pool.resize(1u<<table_rank);
        for(i=old_size; i<pool.size()-1; ++i)
            pool[i].next=i+1;
        pool[i].next=free_list;
        free_list=old_size;
        // And finally need to redo table (rehash entries)
        old_size=(unsigned int)table.size();
        table.resize(1u<<table_rank);
        unsigned int t;
        for(t=old_size; t<table.size(); ++t)
            table[t]=-1; // initially make new lists empty
        int j, *p_j;
        for(t=0; t<old_size; ++t){
            j=table[t]; 
            p_j=&table[t];
            while(j!=-1){
                unsigned int new_t=hash_function(pool[j].key)&table_bits;
                if(new_t!=t){ // j doesn't belong in this list anymore?
                    // delete from this list
                    *p_j=pool[j].next;
                    // add to correct list
                    pool[j].next=table[new_t];
                    table[new_t]=j;
                }else
                    p_j=&(pool[j].next);
                j=*p_j;
            }
        }
    }
    
    bool has_entry(const Key &k) const
    {
        unsigned int t=hash_function(k)&table_bits;
        int i=table[t];
        while(i!=-1){
            if(key_equal(k, pool[i].key))
                return true;
            i=pool[i].next;
        }
        return false;
    }
    
    bool get_entry(const Key &k, Data &data_return) const
    {
        unsigned int t=hash_function(k)&table_bits;
        int i=table[t];
        while(i!=-1){
            if(key_equal(k, pool[i].key)){
                data_return=pool[i].data;
                return true;
            }
            i=pool[i].next;
        }
        return false;
    }
    
    void append_all_entries(const Key& k, std::vector<Data>& data_return) const
    {
        unsigned int t=hash_function(k)&table_bits;
        int i=table[t];
        while(i!=-1){
            if(key_equal(k, pool[i].key)) data_return.push_back(pool[i].data);
            i=pool[i].next;
        }
    }
    
    Data &operator() (const Key &k, const Data &missing_data)
    {
        unsigned int t=hash_function(k)&table_bits;
        int i=table[t];
        while(i!=-1){
            if(key_equal(k, pool[i].key))
                return pool[i].data;
            i=pool[i].next;
        }
        add(k, missing_data); // note - this could cause the table to be resized, and t made out-of-date
        return pool[table[hash_function(k)&table_bits]].data; // we know that add() puts it here!
    }
    
    const Data &operator() (const Key &k, const Data &missing_data) const
    {
        unsigned int t=hash_function(k)&table_bits;
        int i=table[t];
        while(i!=-1){
            if(key_equal(k, pool[i].key))
                return pool[i].data;
            i=pool[i].next;
        }
        return missing_data;
    }
    
    void output_statistics() const
    {
        std::vector<int> lengthcount(table.size());
        unsigned int t;
        int total=0;
        for(t=0; t<table.size(); ++t){
            int i=table[t], length=0;
            while(i!=-1){
                ++length;
                i=pool[i].next;
            }
            ++lengthcount[length];
            ++total;
        }
        int subtotal=0;
        int maxlength=0;
        for(t=0; t<lengthcount.size() && t<10; ++t){
            subtotal+=lengthcount[t];
            if(lengthcount[t]>0){
                std::cout<<"length "<<t<<": "<<lengthcount[t]<<"   ("<<lengthcount[t]/(float)total*100.0<<"%)"<<std::endl;
                maxlength=t;
            }
        }
        std::cout<<"rest: "<<total-subtotal<<"   ("<<100.0*(1.0-subtotal/(float)total)<<"%)"<<std::endl;
        for(; t<lengthcount.size(); ++t)
            if(lengthcount[t]>0)
                maxlength=t;
        std::cout<<"longest list: "<<maxlength<<std::endl;
    }
};

#endif
